/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Du Zhengchi
 * Date: 2024-04-05
 * Time: 19:48
 */
public class TestDemo1 {
    public static int count = 0;
    /*
    递归方法
     */
    public static int fib(int n) {
        if(n == 1 || n == 2){
            count++;

            return 1;
        }

        return fib(n-1) + fib(n-2);

    }
    /*
    迭代方法
     */
    public static int fib2(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;

        for (int i = 3; i <=n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }

        return f3;
    }

    public static void move(char pos1, char pos2){
        System.out.print(pos1+" -> "+pos2+" " );
    }

    /**
     *
     * @param n 盘子数
     * @param pos1 起始位置
     * @param pos2 中转位置
     * @param pos3 目标位置
     */
    public static void hanio(int n, char pos1, char pos2, char pos3){
        if(n == 1){
            move(pos1, pos3);
        }else{
            hanio(n-1, pos1, pos3, pos2);
            move(pos1, pos3);
            hanio(n-1, pos2, pos1, pos3);
        }
    }
    public static void main(String[] args) {
      /*  System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(400));

        System.out.println(fib(40));
        System.out.println(count);

        System.out.println(fib2(40));*/

        hanio(1, 'A', 'B', 'C');
        System.out.println();
        hanio(2, 'A', 'B', 'C');
        System.out.println();
        hanio(3, 'A', 'B', 'C');
        System.out.println();
        hanio(4, 'A', 'B', 'C');
        System.out.println();
        hanio(5, 'A', 'B', 'C');
        System.out.println();
        hanio(6, 'A', 'B', 'C');
    }
}
